<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 3. Структуры Данных.Base</h2>
<ol>
  <li>Банальные структуры [10 минут]</li>
  <ol>
    <li>Двусвязный список</li>
    <li>Односвязный список, по которому можно ходить в обе стороны (меньше памяти, чем в двусвязном)</li>
    <li>Cтек, очередь и дек на циклическом массиве.</li>
    <li>Частичные суммы 1d и 2d.</li>
  </ol></li>
  <li>СНМ</li>
  <ol>
    <li>На списках O(m + nlogn)</li>
    <li>На деревьях O(m*) (сжатие путей и подвешивать меньшее к большему, каждая оптимизация по отдельности работает за O(logn))</li>
    <li>Док-во того, что если подвешивать меньшее к большему, получается O(logn): высота не более logn.</li>
  </ol></li>
  <li>RMQ и LCA</li>
  <ol>
    <li>Sparse Table (5 минут)</li>
    <li>Проверка в Online за O(1) того, что одна вершина дерева является предком другой</li>
    <li>LCA двоичными подъемами за O(logn) двумя способами, минимум на пути дерева за O(logn)</li>
    <li>LCA в Offline за O(n*)</li>
    <li>RMQ в Offline за O(n*) (короткий код со стэком)</li>
    <li>RMQ на стеке за O(1)</li>
    <li>RMQ на очереди за O(1)</li>
    <li>LCA через RMQ</li>
    <li>RMQ через LCA</li>
  </ol></li>
  <li>Дерево отрезков</li>
  <ol>
    <li>Минимум, сумма и "изменение в точке" запросами снизу.</li>
    <li>Короткая реализация, ровно 2n памяти.</li>
    <li>Чем снизу лучше сверху? (меньше константа памяти, меньше константа времени, асимптотика O(len))</li>
    <li>Запросы сверху.</li>
    <li>Групповые операции: += на отрезке (и сумма на отрезке)</li>
    <li>Групповые операции: = на отрезке (и сумма на отрезке)</li>
  </ol></li>
  <li>ScanLine</li>
  <ol>
    <li>Пример1: максимальная возрастающая по двум измерениям последовательность</li>
    <li>Пример2: точка, покрытая максимальным числом прямоугольников (стороны параллельны осям координат).</li>
    <li>Пример3: Offline запрос "количество точек в прямоугольнике" за O(logn)</li>
  </ol></li>
</ol>
